package quickSort;

import java.util.List;

/**
 * 快速排序实现
 */
public class QuickSort {

    /**
     * 快速排序实现
     * @param list 需要排序的集合
     * @param start 开始下标
     * @param end 结束下标
     * @return 返回排序好的集合
     */
    public static List<Integer> quickSort(List<Integer> list,int start,int end){
        int i,j,temp;
        i = start;
        j = end;
        //基准值
        temp = list.get(start);
        //先将基准值放在中间的位置上
        while (i < j){
            while(temp <= list.get(j) && i < j){
                j--;
            }
            while(temp >= list.get(i) && i < j){
                i++;
            }
            //交换
            if (i < j){
                int t = list.get(i);
                list.set(i,list.get(j));
                list.set(j,t);
            }
        }
        //交换基准值
        list.set(start,list.get(i));
        list.set(i,temp);
        //递归 分治排序
        if (i-1 > start) list = quickSort(list,start,i-1);
        if (j+1 < end) list = quickSort(list,j+1,end);
        return list;
    }
}
